//
// Description: 5943. 删除链表的中间节点
// Created by Loading on 2021/12/5.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

ListNode *deleteMiddle(ListNode *head) {
    if (!head || !head->next) {
        return nullptr;
    }

    // 快慢指针
    auto slow = head;
    auto fast = head->next;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // 循环结束后，slow 指向要被删除的节点的前一个节点
    slow->next = slow->next->next;

    return head;
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    auto head = generateListNode(nums);

    auto res = deleteMiddle(head);
    while (res) {
        cout << res->val << ' ';
        res = res->next;
    }

    return 0;
}